package leetcode.editor.cn.dsa25_toposort;
//给定一个整数矩阵，找出最长递增路径的长度。
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
//
// 示例 1: 
// 输入: nums =
//[
//  [9,9,4],
//  [6,6,8],
//  [2,1,1]
//] 
//输出: 4 
//解释: 最长递增路径为 [1, 2, 6, 9]。 
//
// 示例 2: 
// 输入: nums =
//[
//  [3,4,5],
//  [3,2,6],
//  [2,2,1]
//] 
//输出: 4 
//解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
// 
// Related Topics 深度优先搜索 拓扑排序 记忆化 
// 👍 401 👎 0

import java.util.LinkedList;
import java.util.Queue;

public class LongestIncreasingPathInAMatrix329_2 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int m, n; // 矩阵的长和宽
        // 以当前节点为坐标中心，分别向左右上下四个方向查找邻接点
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        public int longestIncreasingPath(int[][] matrix) {
            if ((m = matrix.length) == 0
                    ||(n = matrix[0].length) == 0) return 0;
            // 1.统计每个节点的入度
            int[][] indegrees = new int[m][n];
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    for(int[] dir : dirs) {
                        int newRow = i + dir[0], newColumn = j + dir[1];
                        if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n
                                && matrix[newRow][newColumn] < matrix[i][j]) {
                            ++indegrees[i][j];
                        }
                    }
                    // 2.找到入度为0的所有节点，存放到队列中（入队）
                    if (indegrees[i][j] == 0) queue.offer(new int[]{i, j});
                }
            }
            // 3.入度为0的节点依次出队，删除它们的所有的出边，并将新产生的入度为0的节点入队
            int res = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) { // 只出队当前深度的节点
                    int[] cell = queue.poll();
                    int row = cell[0], column = cell[1];
                    for(int[] dir : dirs) {
                        int newRow = row + dir[0], newColumn = column + dir[1];
                        // 邻居节点存在且大于当前节点
                        if (newRow >= 0 && newRow < m && newColumn >=0 && newColumn < n
                                && matrix[newRow][newColumn] > matrix[row][column]) {
                            // 删除出边，将新的入度为0的节点入队
                            if (--indegrees[newRow][newColumn] == 0)
                                queue.offer(new int[]{newRow, newColumn});
                        }
                    }
                }
                res++; // 每删除一个深度（层）所有节点的出边，长度+1
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}